use std::cmp;

/**
 * 面试题 16.06. 最小差
给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差
*
示例：
输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
输出：3，即数值对(11, 8)

提示：
1 <= a.length, b.length <= 100000
-2147483648 <= a[i], b[i] <= 2147483647
正确结果在区间 [0, 2147483647] 内
 */

/**
 * 思路：
 * step 1 先排序
 * step 2 a[x]-b[y] > 0 说明 a[x] > b[y] 由因为 b是按照升序排列的 所以 a[x]-b[y] 一定大于 a[x]-b[y+1]
 * step 3 a[x]-b[y] < 0 说明 a[x] < b[y] 由因为 a是按照升序排列的 所以 a[x]-b[y] 一定小于 a[x+1]-b[y+1]
 * step 4 根据2 和3条件移动双指针
 */
pub fn smallest_difference(a: Vec<i32>, b: Vec<i32>) -> i32 {
    if a.len() == b.len() && a.len() == 1 {
        return (a[0] - b[0]).abs() as i32;
    }

    let mut at = a.clone();
    let mut bt = b.clone();
    at.sort();
    bt.sort();
    let mut x = 0_usize;
    let mut y = 0_usize;
    let mut res = i64::max_value();
    while x < at.len() && y < bt.len() {
        if at[x] == bt[y] {
            return 0;
        }
        let mut deff = (at[x] - bt[y]) as i64;
        res = cmp::min(deff.abs(), res);
        if deff > 0 {
            y += 1;
        } else {
            x += 1;
        }
    }
    res as i32
}

#[cfg(test)]
mod test {
    use super::smallest_difference;

    #[test]
    fn test() {
        let a = vec![1, 3, 15, 11, 2];
        let b = vec![23, 127, 235, 19, 8];
        smallest_difference(a, b);
    }
}
